class Graph {
  constructor(list) {
    this.vertices = []
    this.edges = new Map()
    if (list && list.length > 0) {
      for (let i = 0; i < list.length; i++) {
        this.addVertex(list[i])
      }
    }
  }

  // 添加顶点
  addVertex(v) {
    this.vertices.push(v)
    this.edges.set(v, [])
  }

  // 添加边
  addEdge(v1, v2) {
    this.edges.get(v1).push(v2)
    this.edges.get(v2).push(v1)
  }

  // 转换为邻接表形式
  toString() {
    let str = ''
    for (let i = 0; i < this.vertices.length; i++) {
      str += this.vertices[i] + ' -> '
      const neighbors = this.edges.get(this.vertices[i])
      for (let j = 0; j < neighbors.length; j++) {
        str += neighbors[j] + ' '
      }
      str += '\n'
    }
    return str
  }
  // 初始化状态颜色
  initializeColor() {
    const colors = []
    for (let i = 0; i < this.vertices.length; i++) {
      colors[this.vertices[i]] = 'white'
    }
    return colors
  }

  // 广度优先搜索(BFS)
  bfs(initV, handler) {
    const colors = this.initializeColor()
    const list = [initV]

    while (list.length > 0) {
      const v = list.shift()
      colors[v] = 'gray'
      handler(v)
      const neighbors = this.edges.get(v)
      for (let i = 0; i < neighbors.length; i++) {
        const w = neighbors[i]
        if (colors[w] === 'white') {
          colors[w] = 'gray'
          list.push(w)
        }
      }

      colors[v] = 'black'
    }
  }
  // 深度优先搜索(DFS)
  dfs(initV, handler) {
    const colors = this.initializeColor()
    this.dfsVisit(initV, colors, handler)
  }

  dfsVisit(v, colors, handler) {
    colors[v] = 'gray'
    handler(v)
    const neighbors = this.edges.get(v)
    for (let i = 0; i < neighbors.length; i++) {
      const w = neighbors[i]
      if (colors[w] === 'white') {
        this.dfsVisit(w, colors, handler)
      }
    }
  }
}

const graph = new Graph(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'])

//3.添加边
graph.addEdge('A', 'B')
graph.addEdge('A', 'C')
graph.addEdge('A', 'D')
graph.addEdge('C', 'D')
graph.addEdge('C', 'G')
graph.addEdge('D', 'G')
graph.addEdge('D', 'H')
graph.addEdge('B', 'E')
graph.addEdge('B', 'F')
graph.addEdge('E', 'I')


// console.log(graph.toString());

let result = ''
const handler = v => {
  result += v + ''
}
// graph.bfs('A', handler)
graph.dfs('A', handler)
console.log('result', result);

